An Introduction to Monads for C++ Programmers

2015-09-11

This website would not be complete without a monad tutorial, so I will use this occasion to write one. This tutorial will be using C++ for a spin, since others have already written tutorials for other programming languages. I find that reasoning about monads in C++ is relatively hard, so this may not be the best way to learn about the concept for the first time; it is more of an exercise to see what monads in C++ could look like. Where appropriate, I will use Haskell-style pseudo-code for clarification.

As a little disclaimer, please bare in mind that what follows may not be completely accurate or complete. For example, at some point I will provide the definitions of return and bind for the Maybe monad and say that the monad definition is complete, without a single mention of functors or applicatives. The goal here is to keep the discussion as simple and focused as possible. For further insights into these concepts, you can find plenty of other resources online.

Why monads?

Explaining monads with no prior motivation as to why we need them would be an exercise in futility. In a purely functional programming language like Haskell, functions are said to be pure. A pure function is a function in the mathematical sense: it maps an input to an output, and does nothing else. Pure functions are referentially transparent: replacing a function with its expression leaves the program’s semantics unaltered. Given the same input, a pure function always yields the same output, no matter how many times the function is applied to that input. In addition, pure functions have no side effects: they do not write to the console, talk over the network, or read/write any kind of global, mutable state. Consequently, a compiler has the freedom to evaluate independent computations in whatever order it feels like.

In many situations, however, we need order: read X, then evaluate f(X), and only then write the result to the console. Bringing order to chaos and performing side effects in a specific context is exactly what monads allow us to do.

What is a Monad?

Intuitively, a monad can be defined as a computation mechanism that allows us to sequence actions in a context. The key words here are sequence and context.

Sequence

Monads help us solve the problem of running computations in a specific order. That is exactly what we mean by sequence: do x, then y, then z. As a C++ programmer, you should feel at home with this concept:

int x = 2+3;
int y = f(x);
std::cout << "y is " << y;

Here we have a sequence of statements. We tell the computer to compute 2+3 and assign the result to x, then assign f(x) to y, and then show the result on the console, all in that particular order. The concept of sequence in monads is exactly the same.

But why do we need anything special to run statements in a sequence?. After all, a C++ program is, essentially, a sequence of statements. Remember where we are coming from: a world in which functions are so well behaved (functions are pure) that the underlying machine has much freedom as to the order in which to evaluate them in. Monads allow us to determine that order.

When describing monads, we often use the word monadic action to refer to an action, computation, step or statement in a sequence of statements. We can use all of these terms interchangeably to refer to each of the statements in a sequence like the above code snippet. A monadic action is to monads what a function is to regular computations: the basic building block with which we build more complex computations.

Context

The context is what allows side effects to take place, solving our second problem. Let’s see what this means exactly by moving on to the definition of our first monad.

The Maybe Monad

The Maybe monad allows us to sequence actions in the context of failure. That is, an action in the Maybe monad can either yield a value or result in failure. This allows us to express computations that may go wrong and fail, such as taking the head of an empty list.

In C++, we could start by defining the following Maybe data type:

template <typename a>
struct Maybe
{
    std::shared_ptr<a> value;

    // Evaluate the monadic action and yield its value
    const a& operator() () const
    {
        return *value;
    }
};

The Maybe struct is a little container that may or may not contain a value, depending on the state of its internal pointer. However, to fully understand monads, we should not think of Maybe just as a container, but rather as a special kind of computational entity, as hinted by the addition of a function operator. The function operator returns the value being pointed to, assuming that it exists. This gives Maybe objects a new spin: they can be treated as something we can call or evaluate to yield a value. This is what we mean by “computational entity”, or “function object” in plain C++ terms. In addition, Maybe objects will have special denotations. A Maybe<a> object containing a null pointer will denote a failed computation, whereas a Maybe<a> object with an initialised pointer will denote a successful computation that yields a value of type a. These are denotations that we give to Maybe; they don’t mean anything to a compiler. Think of Maybe, then, as a special kind of function object or computational entity that may potentially yield a value depending on the state of its internal pointer.

At this point, we can introduce some new vocabulary. As discussed, a Maybe value can be seen as a special kind of computational entity, and we just happen have a word for it. We say that a Maybe object is a monadic value or monadic action. It is a value because it is really just another object in memory that we can store and pass around, like an int or an std::vector. It is an action because the Maybe object is also a function object, so we can look at it as something we can evaluate by calling its function operator to yield a value.

To construct Maybe values, we define two functions, Nothing and Just, which construct failed and successful computations, respectively:

// Construct a Nothing value, denoting failure
template <typename a>
Maybe<a> Nothing ()
{
    return Maybe<a>(); // null pointer, empty value / failed computation
}

// Construct a Just value, denoting a successful computation
template <typename a>
Maybe<a> Just (const a& x)
{
    Maybe<a> maybe;
    maybe.value.reset(new a(x));
    return maybe;
}

The function names Nothing and Just help us with readability. The Nothing function constructs empty Maybe values, which stand for failed computations, hence the word Nothing. The Just function, on the other hand, constructs Maybe values that contain an internal value. These non-empty Maybe values represent successful computations that just yield the value we pass to the Just function, hence the name Just. The functions Nothing and Just therefore construct failed and successful Maybe computations, respectively.

I defined the Nothing and Just functions instead of adding two constructors to the Maybe struct because we cannot give constructors a name, and I really wanted these constructor functions to have a proper name. The reason is that we can now perform an exercise that is very common in functional programming: we will refer to values constructed with the Nothing function as Nothing values, and to values constructed with the Just function as Just values. Thus, the distinction between the functions and the values they yield becomes very blurry; this is functional programming.

From this point on, when we talk about Nothing or Just, it will not matter whether we are referring to the functions or to values constructed with those functions. The expression Just(3) can be regarded as a function call to the Just function with value 3, or as a Maybe value that yields a 3 (the Just function returns a Maybe value). Similarly, the expression Nothing() can be viewed as a function call to the Nothing function, or as a Maybe value denoting a failed computation. Function and value are equal.

Let us wrap up by exercising our new vocabulary. A Nothing value, named after the Nothing function, represents a failed computation. A Just value, named after the Just function, represents a successful computation. We say that a Maybe<a> value represents a computation that can either yield Nothing or Just<a> value, hence the words Maybe, Just and Nothing in the definitions above. A Maybe value can also be called a monadic value or monadic action, depending on how we want to think about it.

Are you still thinking of Maybe as a simple container at this point, or is it starting to look a bit more magical? In a few moments we will see how Nothing and Just work as failed and successful computations.

Having defined the Maybe struct together with the Nothing and Just functions, we can now create some example monadic values or actions:

Maybe<int> x = Just(3);   // A successful computation that yields value 3
Maybe<int> y = Nothing(); // A failed computation

So far we have defined what the Maybe monad looks like, but we have not defined how it behaves. This behaviour is what will shed light on the real meaning of Nothing and Just. For a monad definition to be complete, we must define two basic operations.

return

The return function takes a value of type a and yields a monadic value Maybe<a>:

template <typename a>
Maybe<a> ret (const a& x) // I am calling the function `ret` because
{                         // `return` is a special keyword in C++.
    return Just<a>(x);
}

If we look at Maybe as a container, we can say that return takes a simple value and puts it in a Maybe. This is like taking a value and using push_back to add it to an std::vector. But we should not think of Maybe as just another container.

If we look at Maybe as a special kind of computational entity, then the return function takes a simple value and wraps it in the Maybe monad. The return function answers the question - “What is the simplest computation that this monad can express?” - In the particular case of the Maybe monad, the simplest computation is one that takes a value a and yields Just<a> value.

Another way of seeing the return function is as a function that takes a simple value and puts it in the context of the Maybe monad. Remember when we said that monads allow us to sequence actions in a context? The return function allows us to take a simple value and lift it into the context of the Maybe monad. It transforms a value of type a into a monadic value or monadic action Maybe<a> that yields that value when evaluated (its function operator is called on).

You might have noticed that return is just Just with another name. The definition of return for the Maybe monad just happens to be that simple :)

An example of return in action:

Maybe<int> x = ret(3); // Just<int>(3)

bind

Context and sequence, those are the two key words in the definition of a monad. The return function allows us to put values into context. Another function, bind, allows us to sequence actions in that context.

The bind function takes a Maybe<a> and a function from a to Maybe<b>, and then applies the function to the a value contained in the Maybe<a> to yield a Maybe<b>:

template <typename a, typename b>
Maybe<b> bind (const Maybe<a>& x,
               const std::function<Maybe<b>(const a&)>& f)
{
    if (is_nothing(x))
        return Nothing<b>();
    else
        return f(x());
}

where

// Return true if the Maybe value is Nothing, false if it is Just a value.
template <typename a>
bool is_nothing (const Maybe<a>& x)
{
    return x.value.get() == nullptr;
}

Note that if the input Maybe<a> is Nothing, then there is nothing to apply the function to (the internal pointer is null) and bind simply yields Nothing. If, on the other hand, the input Maybe<a> value is Just<a> value (the internal pointer actually points to something), then bind applies the function to the a value inside of it, yielding a Maybe<b> value. In Haskell:

bind :: Maybe a -> (a -> Maybe b) -> Maybe b
bind Nothing f = Nothing
bind (Just x) f = f x

This completes the definition of the Maybe monad.

Visualising the Maybe Monad

At this point, you might be asking yourself what have we actually done. You understand the Maybe struct and the Nothing and Just functions, as well as return and bind. But you still do not see how a Maybe value is supposed to represent any kind of computation beyond a function object we can call, or what role the return and bind functions play at all. That is fine. What I wanted to illustrate is how relatively simple the definition of the Maybe monad is. The monad’s true power manifests itself when we put it to use.

Recall the definition of the bind function:

template <typename a, typename b>
Maybe<b> bind (const Maybe<a>& x,
               const std::function<Maybe<b>(const a&)>& f)
{
    if (is_nothing(x))
        return Nothing<b>();
    else
        return f(x());
}

Binding Nothing to a function yields Nothing. Binding Just<a> value to a function yields the result of applying that function to the a contained in the Just<a>, which is itself another monadic value, now of type Just<b>. In other words, if the input Maybe<a> is a failed computation, or Nothing, bind propagates the failure and yields Nothing. In contrast, if the input Maybe<a> is a successful computation, or “Just<a> value”, then bind runs the next step in the sequence by applying the function to the a in the Just<a> to yield a Just<b>.

And now we can repeat the process. The Just<b> value can itself be passed to bind again together with another function to yield a Just<c> value. And the Just<c> can then again be transformed with bind into Just<d>. Or maybe this last computation fails, yielding Nothing, in which case binding this failed Maybe<d> value to the next step in the computation will also yield Nothing. And the Nothing will propagate down the chain to make the entire sequence of monadic actions yield Nothing, denoting that the overall computation has failed. If one action in the sequence fails, the entire sequence fails. If all of the actions are successful, the sequence yields the last value in the chain. Welcome aboard, we have just defined computations under the context of failure. Let’s illustrate the Maybe monad in action with some examples.

Defining functions in the Maybe monad

Consider a function to divide an integer x by an integer y:

int div (int x, int y)
{
    if (y == 0)
        // what here?
    else
        return x/y;
}

Division is defined for all pairs of integers except when the denominator is 0. What is the div function supposed to yield in that case? As a C++ programmer, you might opt for throwing an exception. That is perfectly fine. In fact, exceptions are just another monad, and the entire C++ language itself can be seen as one big monad. Since we want to illustrate how the Maybe monad works, however, let us represent failure using Maybe:

Maybe<int> div (int x, int y)
{
    if (y == 0)
        return Nothing<int>(); // Nothing denotes failure
    else
        return Just(x/y); // Just denotes success
}

Notice how the div function now yields a value of type Maybe<int> instead of just a plain int. When we do this, we say we that have lifted the function into the Maybe monad. If the denominator is 0, the div function yields Nothing, otherwise it yields Just the result of the division x/y. Even though division is not defined for every pair of integers, the Maybe monad does allow us to write div as a total function. The Maybe monad allows us to handle the failure case when y=0.

Finally, let us define a function that increments a number by one, just for illustration purposes:

Maybe<int> inc (int x)
{
    return Just(x+1);
}

The inc function always returns a Just value, since there is no failure case here. This is perfectly valid; we never said that actions in the Maybe monad have to fail.

Having these two functions in hand, let us see how we can thread or sequence computations in the Maybe monad together with bind.

Sequencing computations with bind

Remember that bind takes a Maybe<a> value, a function from a to Maybe<b>, and returns a Maybe<b>:

template <typename a, typename b>
Maybe<b> bind (const Maybe<a>& x,
               const std::function<Maybe<b>(const a&)>& f)
{
    if (is_nothing(x))
        return Nothing<b>();
    else
        return f(x());
}

A value of type Maybe<a> represents a computation that may or may not yield a value of type a. The bind function allows us to thread computations by taking the a wrapped in these Maybe<a> values and applying a function to it to yield a new monadic value of type Maybe<b>. This new Maybe value can in turn be fed as an input to the next computation, and the result of that computation to the next one, and so on. But remember that monads sequence actions in a context. The context in the case of the Maybe monad is failure. If bind comes across a Nothing - a failed computation - then the entire sequence of actions results in Nothing, or failure. If everything goes well, bind yields the expected result wrapped in a Just.

The following examples use bind to feed Maybe int values to functions taking plain int values and yielding Maybe int values:

Maybe<int> a = bind(ret(2), inc); // Just(3)
Maybe<int> b = bind(bind(ret(2), inc), inc); // Just(4)
Maybe<int> c = bind(ret(4), std::bind(div, _1, 2)); // Just(2)

In the first example, we take value 2 and lift it into the monad with ret. This results in a Just(2) value, a computation yielding a 2. This Just(2) value is fed to bind together with inc. The result is that the 2 in the Just(2) is incremented, resulting in a Just(3). To see why this happens, use the definitions of ret, bind and inc and substitute them in:

bind (ret(2), inc) = bind (Just(2), inc) = inc(2) = Just(3)

In the second example, we inject 2 into the monad to obtain Just(2). The Just(2) value is fed to bind together with inc. This yields Just(3). The value 3 contained in the Just(3) is once again fed to bind with inc, yielding a final result of Just(4). Again, apply substitution to see how this works:

  bind ( bind (ret(2), inc), inc )
= bind ( bind (Just(2), inc), inc )
= bind (inc(2), inc)
= bind (Just(3), inc)
= inc(3)
= Just(4)

The third example feeds the value 4 wrapped in a Just to a function that divides its argument by 2, yielding Just(4/2) = Just(2).

Sequencing failure

So far so good, but none of the above examples have a failure case. What makes the Maybe monad interesting is that it allows us to deal with failure, so let us see how bind sequences failed computations.

Consider a function that computes (1/x) + 1:

int compute (int x)
{
    return (1/x) + 1;
}

The compute function is undefined for x = 0, so it is unsafe in this form. We can lift the compute function into the Maybe monad to make it safe:

Maybe<int> compute (int x)
{
    std::function<Maybe<int>(const int&)> div_by_x = std::bind(div, _1, x);
    return bind(bind(ret(1), div_by_x), inc);
}

Using the monadic version of compute, we can now apply this function to integer values with no fear of dividing by 0:

Maybe<int> d = compute(1); // Just(2)
Maybe<int> e = compute(0); // Nothing

The first example computes (1/1) + 1 = Just(2). What is more interesting is the second example, which attempts to compute (1/0) + 1. The Maybe monad detects the erroneous division by 0 and yields Nothing in return, denoting that the computation has failed. The value 1 is never divided by 0, so the program does not crash. Maybe handles the failure gracefully and yields Nothing.

To understand how each of these computations work, apply substitutions as usual:

  compute 1
= bind (bind (ret(1),  div_by_1), inc)
= bind (bind (Just(1), div_by_1), inc)
= bind (div_by_1(1), inc)
= bind (Just(1), inc)
= inc(1)
= Just(1)

and

  compute 0
= bind (bind (ret(1),  div_by_0), inc)
= bind (bind (Just(1), div_by_0), inc)
= bind (div_by_0(1), inc)
= bind (Nothing, inc)
= Nothing

The first example is just like the ones in the previous section, in the sense that all computations produce Just values and the final result is the expected value of (1/x) + 1 wrapped in a Just.

The second example is where the Maybe monad manifests its power. When we evaluate compute(0), everything goes well until we attempt to divide 1 by 0:

bind (div_by_0(1), inc)

The div function yields Nothing in this case:

Maybe<int> div (int x, int y) // x = 1, y = 0
{
    if (y == 0) // true
        return Nothing<int>(); // failure
    else
        return Just(x/y);
}

This leaves us with

bind (Nothing, inc)

Now recall the definition of bind:

template <typename a, typename b>
Maybe<b> bind (const Maybe<a>& x,
               const std::function<Maybe<b>(const a&)>& f) // x = Nothing
{
    if (is_nothing(x)) // true
        return Nothing<b>(); // propagate failure
    else
        return f(x());
}

bind finds Nothing in its input and yields Nothing, propagating the failure down the monadic chain:

  bind (Nothing, inc)
= Nothing

The final result is therefore Nothing. One simply cannot divide by 0.

The Side Effects of Maybe

We have said that monads help us solve two problems: determining order and allowing side effects. We have seen how bind solves the order problem by threading or sequencing monadic actions, running one after the other. But at what point were our Maybe actions allowed to have side effects?

A Maybe action is allowed to do two things: yield Just<a> value or Nothing. When a Maybe action results in Nothing, the entire sequence of actions is short-circuited and the overall result is Nothing. This is the side effect that a Maybe action can have. A Maybe action can yield a value just like regular functions, or it can fail the entire computation and make it result in failure. This second nature of monads is what gives them their side effects. In the case of the Maybe monad, the side effect is failure. The Maybe monad therefore allows us to deal with failure.

Aftermath

A monad allows us to sequence actions in a context. The context is what makes one monad different from another. The Maybe monad puts us in the context of failure: a Maybe action can either yield a value or result in failure. This second nature of monads, being able to do something other than computing values, is what allows monadic actions to have side effects. Monads also answer the question of what order to run computations in.

A C++ programmer would typically resolve to exceptions or some other way of signaling failure for the examples presented above. The Maybe monad is less powerful than an exception, because while the Maybe monad will allow you to represent computations that may fail, it will not tell you why the failure occurred. Exceptions, on the other hand, often contain a message describing the problem encountered. It turns out, however, that exceptions in Haskell are just another Monad (called Either, because they can yield either a meaningful value or a descriptive error). The Maybe monad is just one of the many monads that exist, simple enough to be able to write a short tutorial about it. But there are many others, such as the Either monad for exceptions, or the List monad, which describes non-deterministic computations.

The C++ language can be seen as one specific monad. You get to describe your programs in a given way, and that is it. In Haskell, on the other hand, there are many monads, and these can be composed (stacked) to combine their effects. For example, if we wish to describe non-deterministic computations than can fail and talk over the network, we can do just that. Thus, in Haskell we often find ourselves first deciding how we want to represent the solutions to a given problem domain, come up with the right monad, and then actually solve the problem. More generally, we come up with the right abstractions for each problem domain, which may or may not involve monads.

Monads are also often used to limit the side effects a computation may have. We may want write code that can send or receive messages over the network, for example, and be able to do only that. By defining a monad to deal with the specifics of the network, we make sure our network code is not having other side effects, such as writing changes to a database. This makes reasoning about our code much easier, since the monad ensures that the code is doing only the kinds of things it was intended to do.

Moving Forward

If you would like to learn further about these concepts, consider learning you a haskell or reading the Haskell book.

Source Code

The C++ code below contains everything we have seen above. It is a little different from the examples, but it should not deviate too much. More specifically, bind was ambiguous with std::bind, so I renamed it to mbind, and the compiler was also having trouble matching certain types and deducing others.

C++

Haskell

data Maybe a = Just a | Nothing

return :: a -> Maybe a
return = Just

bind :: Maybe a -> (a -> Maybe b) -> Maybe b
bind Nothing _ = Nothing
bind (Just x) f = f x

mydiv :: Int -> Int -> Maybe Int
mydiv _ 0 = Nothing
mydiv x y = Just (x `div` y)

inc :: Int -> Maybe Int
inc = return . (+1)

compute :: Int -> Maybe Int
compute x = Just x >>= \y -> (mydiv 1 y >>= inc)